#include <vcruntime_typeinfo.h>
#include<vector>

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode() : val(0), left(nullptr), right(nullptr)
    {
    }

    TreeNode(int x) : val(x), left(nullptr), right(nullptr)
    {
    }

    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right)
    {
    }
};

class Solution
{
public:
   
    int countNodes(TreeNode* root)
    {
        int h = heightCal(root);
        return scal(root,1,h);
    }
    int scal(TreeNode* root,int level ,int h)
    {
        if (root == nullptr) return 0 ;
        int rh = level+heightCal(root->right);
        if (rh == h)
        {
            return (1 << (h-level)) + scal(root->right,level+1,h);
        }
        else
        {
            return scal(root->left,level+1,h) + (1<<(h-level-1));
        }
    }

    int heightCal(TreeNode* root)
    {
        if (root == nullptr) return 0;
        int sum =1;
        while (root->left!=nullptr)
        {
            root=root->left;
            sum++;
        }
        return sum;
    }
};

